﻿#include <iostream>
using namespace std;


struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
 
class Solution 
{
public:
    // 24. 两两交换链表中的节点
    ListNode* swapPairs(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr)
            return head;

        ListNode* rhead = new ListNode(-1);
        ListNode* prev = rhead, * cur = head;
        while (cur && cur->next)
        {
            ListNode* next = cur->next, * nnext = next->next;
            prev->next = next;
            next->next = cur;
            cur->next = nnext;

            prev = cur;
            cur = nnext;
        }

        ListNode* ret = rhead->next;
        delete rhead;
        return ret;
    }

    // 递归
    /*ListNode* swapPairs(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr)
            return head;

        ListNode* rhead = swapPairs(head->next->next);
        ListNode* tmp = head->next;
        head->next = rhead;
        tmp->next = head;
        rhead = tmp;

        return rhead;
    }*/
};

int main()
{

    return 0;
}